

class UnionSet:

    def __init__(self, n):
        self.parent = [0] * (n + 1)
        for i in range(n + 1):
            self.parent[i] = i

    def get_parent(self, index):
        while index != self.parent[index]:
            self.parent[index] = self.parent[self.parent[index]]
            index = self.parent[index]
        return index

    def union(self, x, y):
        x = self.get_parent(x)
        y = self.get_parent(y)
        self.parent[x] = y
